Suzy B Software 2/Suzy B Software CD-ROM 2 (1994).iso/anidone/3ddemo/matricks.doc

Text File | 1995-05-02 | 28KB | 583 lines

                  Documentation for the graphic functions.
                  ----------------------------------------

                     sources and doc by L.J.M. de Wit

      OBJECTIVE

   The purpose was to supply a number of useful graphic functions that
   can be used in a modest scale for animation, 3D motion, demo's. Another
   purpose was to poke up some discussion conceirning graphic functions,
   representations, etc. I'm only in a minor way involved with graphics in
   my job, so I'm open for any other ideas. The functions offered have not
   the least pretention to be exhaustive, although it would be nice to
   enlarge and enrich the capabilities in future releases. Whoever has ideas,
   remarks, bugs found in the package, questions about the source or how to
   use it, is invited to send them to me; any help is welcome but also gladly
   offered.


      COPYRIGHT AND THE LIKE

   The source can be used freely for non-commercial purposes;
   if you redistribute the source keep my copyright notice in; that's a small
   fee for the effort I've put into it. If you plan to make changes to the
   source and distribute I would like to know; this to prevent duplication of
   effort, and existance of different branches; perhaps redistribution could
   go via me (maybe I'm already too optimistic about others willing to work
   on some part of the code 8-). Also anyone planning to use (part of) it in
   a commercial product should contact me; this be said to keep everyone
   interested! 8-).


      TARGET MACHINES, LANGUAGE USED

   In the present form the demo program runs on Atari STs (1 Meg required).
   The amount of memory is merely required to run the demo that stores a
   series of compressed images; this is the only part that really requires
   memory. It should not be hard to port the code to various machines, notably
   the Mac, the Amiga, the IBM PC with graphics card, a Sun, etc.
   The language used is C; a small part of the code is in 68000 assembler.
   Since this code also has a line drawing routine (for bit mapped display)
   it can even be used on systems with a very limited or no graphics library.


      BREAK UP OF SOURCES

   Currently the following source modules exist:

      matricks.h:    header file for extern declarations and the like.
      3demo.c:       contains main and all demo functions
      mat.c:         operations on matrices
      object.c:      operations on objects: items and instances
      gemfuncs.c:    O.S. dependant part of graphic functions: opening a work-
                     station, swapping screen memory etc.
      mxops.asm:     like mat.c but these are assembler functions.
      drawlin.asm:   function to draw a line.

   The last 3 named are the ones most likely to cause problems when porting.
   If your system doesn't have GEM, gemfuncs.c will have to be rewritten,
   but this is no big deal; if your system uses an other processor than a
   68000 the assembler functions will have to be re-created; also if the
   layout of your bitmap display is different from (any of the) Atari ST,
   the drawlin.asm needs a thorough scan.


      IDEAS ABOUT REPRESENTATIONS ETC.

   In order to give you a better understanding of the source I'll explain
   some of the ideas used in the code and why some choices were made.
      1) Use of matrices for all motions (translation, rotation and any
   combination of these). An object in space can be represented by a set
   of coordinates for each point; if the object consists of a set of lines
   it suffices to store the coordinates of the end points and the way the
   points are connected (the polygons). The coordinates of an object are
   stored per row for each point in a 2D array (the height equals the
   number of points registrated, the width the number of coordinates: 4).
   A motion of the object can now be computed by multiplying the (npoints x 4)
   coordinate array with the (4 x 4) transformation array, resulting in a
   new (npoints x 4) array, representing the new coordinates. Note that in
   case a combination of transformations is applied to the object (e.g.
   a translation followed by a rotation) it is cheaper (in terms of # of
   multiplications) to first multiply the (4 x 4) transformation matrices
   (resulting in a new 4 x 4 matrix) and then multiply the coordinate matrix
   with this one than to multiply the coordinate matrix with each
   transformation matrix separately. This is also one of the reasons that
   using matrix calculus is much cleaner and clearer than using goniometric
   formulas; you do not get lost in long formulas and you can concentrate
   on things that really matter, and the speed gain is vast when you're
   handling several points / several transformations at a time.
      2) Use of 3D projective coordinates to represent a point in 3D space.
   Those interested in but not familiar with these coordinates are advised
   to read an (introductory) book about Projective Geometry; for those that
   are only not familiar with it (and thus not interested 8-), it should
   suffice to say that a point's
   coordinates may all be multiplied with a constant, so for instance
   (1, 2, 5, 7) is the same point as (3, 6, 15, 21) and that the (normal)
   Carthesian coordinate system can be embedded in projective space as
   follows: if (X,Y,Z) is a point in 3D Carthesian it corresponds with
   (X,Y,Z,1) in 3D projective space (note: 4 coordinates). Of course
   you could choose (2.3X,2.3Y,2.3Z,2.3) also or any constant you like.
   The two main advantages of using projective (or homogeneous) coordinates
   that I can see are: a) all motions of a rigid body in space can be
   represented by a matrix (or series of) multiplication(s), or, put
   differently, each transformation can be represented by a matrix.
   b) since homogeneous coordinates are used, the elements of the matrix
   may be scaled with a constant factor. This is an important issue in
   terms of speed, since it allows the use of integers throughout the code
   (many architectures deal faster with integer calculations than float
   and double calculations); yes, by using correctly chosen scaling factors
   (not too small to retain precision, no too big to prevent overflow)
   even shorts are usable (16 bits shorts that is). The 68000 handles
   word (16 bit) multiplications as one instruction, resulting in fast
   performed matrix multiplications. The result matrix is of course a
   matrix with 32-bit elements, but these are scaled afterwards to fit again
   in a short. In fact, the scaling chosen is such that multiplying these
   shorts in pairs and adding 4 such pairs does not overflow a signed long.


      ABOUT OBJECTS

   This being said and understood the notion of the objects used should be
   easy now. Two types of objects are of special interest:
   The item, in fact a pointer to a struct, defined by:

   typedef struct itstruct {  /* item definition: ptr to this struct */
      int count;              /* # of points in this item */
      polygon next;           /* pointer to polygon list */
      WORD r_data[1][4];      /* homogene coordinates of first point; */
   } *item;                   /* the rest follows hereafter */

   Note that only one row of the coordinate matrix is declared; this is to
   allow for arbitrary sized arrays without having to resort to pointers
   (of course the only reasonable usage must be by dynamic allocation of the
   actual struct).
   The 'polygon next' member is a pointer to a linked list of arrays of
   indices, as follows:

   typedef struct polystruct {/* polygon def: ptr to this struct */
      int count;              /* # of points in this polygon */
      struct polystruct *next;/* ptr to next polygon */
      WORD coord[1];          /* index of first point */
   } *polygon;                /* the rest follows hereafter */

   Like with the item def. only one index is declared; in an actual case many
   will follow in consecutive memory. Each polygon is a series of connected
   lines, the indices being the numbers of the points in the coordinate array.
   Thus an item can have several series of connected lines.

   An item is in fact a very static object, it can be seen as an abstraction.
   If we want to use it, we need an other type of object, i.e. the instance.
   An instance is also a pointer to a struct, defined by:

   typedef struct instruct {  /* instance def: ptr to this struct  */
      item in_item;           /* item of which this is an instance */
      WORD trans[4][4];       /* 4H that places it                 */
      WORD i_data[1][2];      /* screen coordinates of first point */
   } *instance;               /* the rest follows hereafter        */

   The 'item' member is the pointer to the corresponding item structure
   (containing a coordinate array and a list of polygons).
   The 'trans' member is the transformation matrix that puts the item in 3D
   space (so its contents varies because it is multiplied each time by
   whatever transformations act on the object).
   To be able to do the calculation of projected points and actual drawing
   of the computed lines in different places, there is also a storage area
   in the instance structure that contains for each point the actual screen
   coordinates (pixel coordinates). So it's written by the projection functions
   and read by the draw functions. Again there's room for one point only,
   but dynamic allocation 'over the edge of the struct' allows for an
   arbitrary number of points. Note that the definition of C says that
   consecutive members of the struct occupy consecutive places in memory, so
   that we may safely use 'the other end' of the struct.


      TERMINOLOGY USED

   To keep things small and simple the following abbreviations will be used:
   4H: 4 x 4 homogeneous transformation (matrix). Unless stated otherwise,
       this will be represented in the machine by a: short [4][4], where
       short is a 16 bit wide integer.
   I, O, IO: in, out, inout - for parameters.

      LIST OF FUNCTIONS AND BRIEF DISCUSSION

   Now follows a list of the functions offered and a tiny description of
   them; consult the source if you want to go into detail, you will find
   this text more or less also there. The functions from the 3demo.c module
   are not listed here since they serve only a demonstration purpose and
   are not suitable for general use.

   From mat.c:

   - note that, unless stated otherwise, memory for matrices etc. must
     already exist, must be either dynamically or statically be allocated.

   o  void matapply(mat,func,v,fac)
      WORD *mat;          IO the 4H to be transformed (e.g. ins->trans).
      WORD *(*func)();    I  the kind of transformation, i.e. a function ptr.
                             func can currently only be mattlate, matrotate,
                             or matreflect.
      double *v;          I  a 3D vector to quantisize the transformation.
      double fac;         I  a number with which v is multiplied.

      Applies a transformation to a 4H. This can be a
      translation, rotation or reflection. Matapply can typically be used
      to create 4H's beforehand that represent a small motion (small
      step in x-, y-, z - direction or turn around x-, y-, z - axis).
      In that case mat is taken to be an 4H identity matrix, v one of the
      unity vectors ((1,0,0), (0,1,0), (0,0,1)) and fac is a (small) number.

   o  void matcompose(a,b)
      WORD *a;            IO
      WORD *b;            I

      The result of the (homogeneous) multiplication of a and b is placed
      into a. This function is implemented as a macro.
      It can be used for instance to update an instance coordinate
      transformation (take a to be ins->trans) when an other transformation
      affects it (the b matrix).

   o  WORD *matident(n,a)
      int n;              I
      WORD *a;            O

      Create a nxn identity matrix and return the pointer to it.

   o  WORD *matreflect(v,a)
      double *v;          I  a quantisizing 3D vector: the normal vector
      WORD *a;            O  the 4H.

      Create a 4H reflection matrix. Used by matapply().

   o  WORD *matrotate(v,a)
      double *v;          I  a quantisizing 3D vector: the rotation axis
      WORD *a;            O  the 4H.

      Create a 4H rotation matrix.

   o  WORD *mattlate(v,a)
      double *v;          I  a quantisizing 3D vector: the translation step
      WORD *a;            O  the 4H.

      Create a 4H translation matrix.

   o  uchar *matscr_to_str(b_and_w)
      bool b_and_w;       I  Use-only-black-and-white flag

      Compress screen into unsigned char array and return pointer to it.
      If the flag is TRUE, the screen is handled as if only one colour was
      present (even if it is multi-colour); this allows for some factors
      extra compaction. The memory needed for the array is dynamically
      allocated.
      The screen information is stored in the following way:
      Assume for simplicity's sake the screen consists of 200 lines, each
      line being 160 bytes wide, so 160 (byte) columns wide (the peculiarities
      of the different resolution and colours will be handled further on).
      The first byte contains the number of nonempty columns that were found.
      Then follows for each nonempty column:
         the column number (0-159)
         the number of line sets (0-80). A line set is a series of consecutive
            nonzero bytes in one column.
         Then follows for each line set:
            the first line of the set (0-199).
            the number of lines (0-199).
            the actual values (each being 0-255)
         until last line set in column
      until last nonempty column on screen.
      As for the different screen modes:
         High res on the Atari has 400 lines, 80 byte columns. To be able
         to deal with the lines from 256 up (the line no. must fit in a byte)
         the lines from 200-399 are marked by using column numbers 160-239
         (instead of 0-79) and line numbers 0-199 (instead of 200-399).
         Medium and low res have both 200 lines. Medium has 80 columns,
         2 colour bit planes, whereas low has 40 columns, 4 colour bit planes.
         Because the colour info is stored as: word0 of plane0, word0 of
         plane1, etc. the simple solution is to view an entire line as simply
         160 bytes (of which there are overlapping pairs for medium and
         overlapping quartets for low res.), so use columns 0-159.
         The b_and_w flag simply says to ignore each odd word in medium res.
         and each second, third and fourth word of four consecutive words in
         low res. In this way, if the image was already black, a compaction
         of 2 to 4 times above the existing compaction is reached.

   o  void matstr_to_scr(s,b_and_w)
      register uchar *s;  I  Array of compressed data
      bool b_and_w;       I  Handle-as-black-and-white-only flag

      Display compressed image. s should have been created by matscr_to_str().

   o  void error(func)
      char *func;         I  name of function in which error occured

      Simple error handling function. Display a message and stop program.

   o  double maxfactor(arr,cnt)
      double *arr;        I  the array
      int cnt;            I  # elements in array

      Find maximal multiplication factor for an array of doubles so that each
      array element after multiplication with this factor can be cast to
      short without truncation.

   o  double mycos(a)
      double a;           I

      Fast cosine function by table lookup. Each value that has been
      calculated once can be retrieved by table lookup.

   o  double mysin(a)
      double a;           I

      As mycos() for sine function.

   From mxops.asm:

   o  void mxhmul(a,b,c,p,q,r)                                                       *
      short *a,           I  points to array of p x q shorts
            *b,           I  points to array of q x r shorts
            *c,           O  points to array of p x r shorts
            p, q, r;

      Matrix multiplication for homogeneous coordinate matrices
      c points to the result of the multiplication of the matrices
      pointed to by a and b. It is scaled to fit in shorts.
      Since a temporary array is used to store intermediate 32 bit
      results c may be one of a, b without a problem.

   o  short *matcopy(a,b,n)
      short *a;           I
      short *b;           O
      short n;            I

      Copy over n shorts from the array pointed to by a to that pointed
      to by b.

   o  void mxproj(inarr,outarr,pcount,eye_z,scal_x,scal_y)
      short *inarr,       I
            *outarr;      O
      short pcount;       I
      short eye_z,        I  distance of observer to screen
            scal_x,       I  scaling along x axis of screen
            scal_y;       I  scaling along y axis of screen

      Projection of inarr onto the instance's screen coordinates outarr.
      inarr points to an pcount x 4 array of shorts representing the hom.
      coordinates of the pcount points of the instance.
      outarr points to a pcount x 2 array of shorts representing the screen
      coordinates to be calculated for each point (this array is part of the
      instance).
      eye_z, scal_x and scal_y are parameters that determine the projection.

   From gemfuncs.c:

   o  void gem_init()

      opens a virtual workstation and allocates extra screen memory for
      smooth drawing.

   o  void gem_exit()

      closes a virtual workstation, restores screen location and exits.
      The allocated memory for a screen is automatically returned to the
      system.

   o  void swapscreen()

      switches the logical and physical screens. All drawing functions
      (including displaying text) takes place on the logical screen, while
      the physical screen is displayed. When the drawing is finished, the
      pointers to the two screen areas are swapped. The VBL (vertical blank
      interrupt routine) checks whether the physical screen pointer has
      changed and if so, tells it the hardware. By altering the physical
      screen location just before the screen is displayed (the beam is aimed
      again at the start of the display it is ensured that movement is smooth
      (no screen memory updating while is it being read).

   From drawlin.asm:

   o  void drawlin(x1,xy1,x2,y2)
      WORD x1,y1,x2,y2;   I

      Draw a line between points (x1,y1) and (x2,y2) in high, medium or low
      resolution. No attempt has been made to handle colours, different line
      styles/widths, clipping, although this should be simple - maybe
      something for a next release.
      The method used for calculating the pixel coordinates of the line is
      Bresenham's algorithm, of which I will give an explanation. Also some
      details of how it is speeded up further wil be given.
      The algorithm consists of taking always a step in the direction of the
      axis of greatest movement, and, depending on an accumulating error term
      also in the direction of smallest movement. A derivation for the simple
      case that the start point is (0,0) and the end point (a,b) with a >= b
      and a and b both >= 0:
      Equation of the line:

                 a . y - b . x = 0                             (1)

      Now take (x(n), y(n)) to be the nth point of the line. Because x(n) and
      y(n) are integers, they will generally not satisfy (1). In fact an error
      term d(n) exists, generally not 0:

                 a . y(n)  - b . x(n)  = d(n)                  (2)

      Since steps are to be taken in x direction, the x(n) is 'correct';
      the y(n) may be off at most 0.5, so

                 - 0.5a <= d(n) < 0.5a.                        (3)

      It is easier to compare against 0, so instead of d(n) we use e(n) with

                 e(n) = d(n) + 0.5a.                           (4)

      and

                 0 <= e(n) < a                                 (5)

      By subtracting (2) from (2) with n+1 instead of n we get:

                 a . (y(n+1) - y(n)) - b . (x(n+1) - x(n))  = d(n+1) - d(n)

      Since x(n+1) - x(n) == 1, and d(n+1) - d(n) == e(n+1) - e(n):

                 a . (y(n+1) - y(n)) - b = e(n+1) - e(n), or

                 e(n+1) = e(n) - b + a . (y(n+1) - y(n))       (6)

      Now it's easy, since the e(n+1) must be >= 0  (5), and y(n+1) - y(n)
      is either 1 or 0:
      subtract b from e(n); if result < 0 increment y and add a to error term.

      In a C program:

      short x,y,a,b,e;

      e = a >> 1; /* d(0) == 0, so e(0) == 0.5a */
      y = 0;

      for (x = 0; x <= a; x++) {
         plot(x,y);
         if ((e -= b ) < 0) {
            y++;
            e += a;
         }
      }

      The 'real' thing must also handle the other cases: b > a, a < 0 or
      b < 0:
      First end and starting point are swapped if x2 < x1, so that always
      x2 >= x1; this implies a > 0. The increment of y is 1 if b >= 0,
      -1 if b < 0 and furthermore b is then set to its absolute value.
      The cases a >= b and b > a are dealt with separately.
      Because the machine addresses bytes, not bits, and thus in order to
      avoid excessive address calculations, the pixel (x,y) is represented
      by a word address and a bit in that word. Stepping in x direction is
      done by rotating the word by 1, incrementing/decrementing the address
      if a carry is generated. Stepping in y direction is done by
      adding/subtracting the number_of_bytes_per_line to the address
      (effectively stepping a line).
      The new point is OR-ed into the screen each time; in fact, this OR-ing
      is done into a data register for speed; the actual storing into the
      screen is done when the address is about to change. In the case that
      b > a, the y-step is always taken, so the OR-ing into the data reg. is
      NOT done there.
      An even faster version of drawlin is being planned, but implementing
      it would postpone the current distribution. Next release!

   From object.c:

   o  item matcrit(n,d,o)
      int n;              I  the point count
      double d[][3];      I  the n*3 coordinates of the points
      short *o;           I  an array of indexes for the points; each -1 value
                             ends a joined set of points, an extra -1 ends the
                             array.

      Create an item by giving its point count, point coordinates and order.
      The function allocates memory for the item, in this it stores the point
      count, the points homogeneous 4D coordinates and a polygon list pointer.
      For each polygon also memory is allocated to contain a count and an
      array of indices.

   o  void matfrit(ip)
      item ip;            I  item to be freed

      Frees all memory belonging to the item that was allocated by matcrit.

   o  instance matcrins(it,lia,tv)
      item it;            I  the item it's refering to.
      double lia[3][3];   I  the 3x3 transformation array.
      double tv[3];       I  the translation vector.

      Create an instance of the item by giving the item and a transformation
      matrix to put it into space. Note that the transformation array is an
      array of 3x3 doubles (non-homogeneous coordinates), and also the
      translation vector is in non-homogeneous coordinates. The memory
      allocated will contain a pointer to the item, a 4H to place the item
      in space, and an array to hold the screen coordinates of each point of
      the instance.

   o  void matfrins(ins)
      instance ins;       I  instance to be freed

      Frees all memory belonging to the instance that was allocated by
      matcrins.

   o  WORD *matseteye(lia,tv,dist,sx,sy)
      double lia[3][3];   I  the transformation to orientate the screen
      double tv[3];       I  the vector to place the screen
      double dist;        I  the distance of the eye from the proj. screen
      double sx,sy;       I  scaling for X-, resp. Y-axis.

      Fix the eye and projection screen positions and orientations and scaling.
      This generally has to be done once, unless the eye or proj. screen are
      moving.

   o  void matproject(ins)
      register instance ins; I  the instance to be projected.

      Project an instance, i.e. calculate the screen coordinates it will need
      to draw it. This will fill the array of screen coordinates within the
      instance with values that depend on the current contents of the
      instance's 4H transformation and the observer's position (set by
      matseteye). The critical part is handled by mxproj for speed reasons.

   o  void matdraw(ins,mode)
      instance ins;       I  the instance to be drawn.
      int mode;           I  the mode of drawing (OR,XOR,ERASE etc.)

      Draw an instance, using VDI. Each polygon in the instance's item's
      polygon list is drawn, using the coordinates in the instances screen
      coordinates array.

   o  void matfdraw(ins,mode)
      instance ins;       I  the instance to be drawn.
      int mode;           I  the mode of drawing (OR,XOR,ERASE etc.)

      Draw an instance, using drawlin. The mode parameter is currently ignored.
      See also matdraw. This method is faster; an even faster method for
      drawing lines than drawlin is planned.

   o  void insstore(ins,a,n)      stores
      instance ins;       I  into
      WORD *a;            O  as entry number
      int n;              I  ; i.e. there are n WORDs in a preceding.

      Store the calculated screenpoints of an instance.
      The screen coordinates are stored in a as a[n], a[n+1] etc.
      In this way line images can be stored with minimum overhead. The only
      processing that needs to be done afterwards is calling insload and
      matfdraw (or matdraw). Before insstore is called the coordinate array
      has to be calculated, preferably with matproject.

   o  void insload(ins,a,n)    loads
      instance ins;       I  from
      WORD *a;            I  as entry number
      int n;              I  ; i.e. there are n WORDs in a preceding.

      Recall the calculated screenpoints of an instance. See also insstore.

   o  static WORD *matliatv(invers,lia,tv,rotra)
      int invers;         I  Use inverse of lin. transf.
      double lia[3][3],   I  Linear transform. to place it
             tv[3];       I  Translation vector to place it
      WORD *rotra;        O  4H result

      Apply linear transformation and translation. Note that this function is
      static and can thus not be used as external function. Use matapply for
      a function with comparable capabilities; the difference is that
      matliatv can specify all kinds of linear transformations, and that it
      puts the result in rotra, while matapply is restricted to translation,
      rotation and reflection and applies the thus created 4H upon the output
      4H.

   o  WORD *matseteye(lia,tv,dist,sx,sy)
      double lia[3][3],   I  Linear transform. to place it
             tv[3],       I  Translation vector to place it
             dist,        I  Distance eye from screen
             sx,sy;       I  Scaling x and y axis

      Set eye coordinates. Besides setting distance and scaling the function
      returns a pointer to the (static) 4H observer matrix.